package com.jietuo.class04;

import java.util.Arrays;

/**
 * @author zhangx & jietuo_zx@163.com
 * @version 1.0
 * @date 2024/3/5
 * @description: 堆排序
 */
public class Code03_HeapSort {

    public static void main(String[] args) {
        int[] arr = new int[]{3, 5, 8, 23, 23, 44, 5, 756};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void heapSort(int[] arr) {
        // 可以将这个arr，构造成大根堆，然后每次pop出来就是最大的值，然后在反转？
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
//        for (int i = arr.length - 1; i >= 0; i--) {
//            heapify(arr, i, arr.length);
//        }
        // 这个时候组成了大根堆 ，pop一个，然后加入新数组后面
        int heapSize = arr.length - 1;
        while (heapSize >= 0) {
            swap(arr, 0, heapSize);
            heapify(arr, 0, --heapSize);
        }
    }
    // 插一个数到数组中，转为大根堆，即移动数组最后一个数字
    // 向上升
    private static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    // 向下沉
    private static void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            // 看取左叶子还是右叶子
            // 取右叶子的条件 1） 右叶子存在 即 left + 1 < heapSize
            //              2)  右叶子位置上的数大于左叶子上的数
            //  ---------- 否则取左叶子
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            // 拿到左右叶子的最大值，然后跟插入的数据比较，小的向下沉
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            // 如果index 比largest大，说明刚插入的数据需要下沉
            // 则将 index 和 largest 交换位子
            swap(arr, index, largest);
            // 更新index位子
            index = largest;
            // 更新 left值
            left = index * 2 + 1;
        }
    }

    private static void swap(int[] arr, int index, int largest) {
        int temp = arr[index];
        arr[index] = arr[largest];
        arr[largest] = temp;
    }
}
